'''
Created on Feb 21, 2013

@author: Artur
'''

import random as rnd
from math import floor
from time import clock
from scipy.stats import chisquare


rand5_calls = 0
rand5_time = 0.0

class Branch():
    def __init__(self, offset):
        self.offset = offset
        self.next = {}


def rand5():
    global rand5_calls, rand5_time
    rand5_calls +=1
    t1 = clock()
    r = rnd.randrange(0, 5)
    rand5_time += clock() - t1
    return r


def rand7():
    s = 0.0
    div = 7.0
    while True:
        i = rand5()
        div = div / 5
        s = s + i * div
        r = floor(s)
        n = floor(s + div)
        if not r < n or (r == 6 and n == 7):
            return r
        

cachehit = 0
cachemiss = 0
depthsum = 0
maxdepth = 0

stateCache = Branch(0)
div = [7.0 / 5]

def InitStateTree(maxdepth):
    q = [stateCache]
    
    j = 0
    while j <= maxdepth:
        
        q2 = []
        for state in q:
            if type(state) == Branch:
                for i in range(5):
                    if len(div) <= j:
                        div.append(div[j - 1] / 5)
                        
                    newOffset = state.offset + i * div[j]
                    result = floor(newOffset)
                    nextint = floor(newOffset + div[j])
                    
                    if result == nextint or (result == 6 and nextint == 7):
                        state.next[i] = result
                    else:
                        newBranch = Branch(newOffset)
                        state.next[i] = newBranch
                        q2.append(newBranch)
        
        q = q2
        j = j + 1
        

def rand7_cached():
    global cachehit, cachemiss, depthsum, maxdepth
    
    state = stateCache
    
    j = 0
    while True:
        i = rand5()
        #print(i, end=' ')
        
        if i in state.next:
            cachehit += 1
            #print('hit', end=', ')
            nextState = state.next[i]
            if type(nextState) is not Branch:
                depthsum += j
                if j > maxdepth: maxdepth = j
                #print('return {}'.format(nextState))
                return nextState
        else:
            #print('miss', end=', ')
            cachemiss += 1
            if len(div) <= j:
                div.append(div[j - 1] / 5)
                
            newOffset = state.offset + i * div[j]
            result = floor(newOffset)
            nextint = floor(newOffset + div[j])
            
            if result == nextint or (result == 6 and nextint == 7):
                state.next[i] = result
                depthsum += j
                if j > maxdepth: maxdepth = j
                #print('return {}'.format(result))
                return result
            else:
                state.next[i] = Branch(newOffset)
                
        state = state.next[i]
        j = j + 1
        
        

def rand7_python():
    return rnd.randrange(0, 7)
        
        
def rand7_table():
    T = [
        [ 0, 1, 2, 3, 4 ],
        [ 5, 6, 0, 1, 2 ],
        [ 3, 4, 5, 6, 0 ],
        [ 1, 2, 3, 4, 5 ],
        [ 6, None, None, None, None ]
    ]

    r = None;
    while r == None:
        i = rand5();
        j = rand5();
        r = T[i][j];

    return r


def rand7_reject():
    while True:
        i = 5 * rand5() + rand5()
        if i < 21:
            return i % 7


def StateTreeSize(s):
    levels = []
    nodesum = 0
    q = [s]
    while q:
        levels.append(len(q))
        nodesum += len(q)
        q2 = []
        for node in q:
            if type(node) is Branch:
                for i in node.next:
                    q2.append(node.next[i])
        q = q2
    
    return (nodesum, levels)
        

if __name__ == '__main__':
    
    
#    def DryRun(n):
#        for _ in range(n):
#            rand7_table()
#    
#    
#    import cProfile   
#    import pstats    
#    cProfile.run('DryRun(1000000)', 'prof')
#    p = pstats.Stats('prof')
#    p.strip_dirs().sort_stats('time').print_stats(20)
#    p.strip_dirs().sort_stats('cumulative').print_stats(20)
    
    
#    c = {x : 0 for x in range(7)}
#    for _ in range(1000):
#        c[rand7_cached()] += 1
#    print(c)
    
    
#    n = 10000000
#    for _ in range(n):
#        rand7_cached()
#    print(n, cachehit, cachemiss, cachehit/cachemiss, StateTreeSize(stateCache))
    
    
#    k = 100
#    
#    for n in [10**x for x in range(8)]:
#        
#        hitmiss = 0.0
#        runtime = 0.0
#        avgdepth = 0.0
#        maxdepthtot = 0.0
#        
#        for _ in range(100):
#            cachehit = 0
#            cachemiss = 0
#            stateCache = Branch(0)
#            div = [7.0 / 5]
#            depthsum = 0
#            maxdepth = 0
#            
#            t1 = clock()
#            for _ in range(n):
#                rand7_cached()
#            t = clock() - t1
#            
#            hitmiss += cachehit/cachemiss/(n/1000)
#            runtime += t/(n/1000)
#            avgdepth += depthsum/n
#            maxdepthtot += maxdepth
#            
#        print('{:<10}{:<10.3f}{:<10.5f}{:<10.5f}{:<10.5f}'.format(
#              n, hitmiss/k, runtime/k, avgdepth/k, maxdepthtot/k))
        


    n = 1000
    k = 1000
    
    algs = {'Mine': rand7,
            'Mine 2': rand7_cached,
            'Python': rand7_python,
            'Table': rand7_table,
            'Reject': rand7_reject,
            }
    
    outf = '{:<10}{:<10}{:<10}{:<10}{:<10}'
    out = outf.format('Method', 'P-Value', '#Rand5', '%Rand5', 'Run Time')
    print(out)
        
    for alg in algs:
        score = 0.0
        rand5_calls = 0
        rand5_time = 0.0
        
        runtime = 0.0
        for _ in range(k):
            c = {x : 0 for x in range(7)}
            time1 = clock()
            for i in range(n):
                c[algs[alg]()] += 1
            runtime += clock() - time1
                
            (chi, pval) = chisquare(list(c.values()))
            score += pval
            
        outf = '{:<10}{:<10.3f}{:<10.3f}{:<10.2%}{:<10.3f}'
        out = outf.format(alg, score / k,  rand5_calls / n / k, 
                          rand5_time/runtime, runtime)
        print(out)
        
        
        
        
        
        
        
        
        
        
        